package demo1;

import java.util.Arrays;
import java.util.Scanner;

public class MajorityElement {
    static class Result {
        int number;// 众数
        int count;// 重数

        Result(int number, int count) {
            this.number = number;
            this.count = count;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入元素个数n:");
        int n = scanner.nextInt();
        int[] arr = new int[n];
        System.out.println("请输入" + n + "个整数:");
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        Arrays.sort(arr);

        Result result = findMajority(arr, 0, n - 1);
        System.out.println("众数: " + result.number);
        System.out.println("重数: " + result.count);

        scanner.close();
    }

    public static Result findMajority(int[] arr, int left, int right) {
        if (left == right) {
            return new Result(arr[left], 1);
        }

        int mid = (left + right) / 2;
        Result leftResult = findMajority(arr, left, mid);
        Result rightResult = findMajority(arr, mid + 1, right);

        if (leftResult.number == rightResult.number) {
            return new Result(leftResult.number, leftResult.count + rightResult.count);
        }

        int leftCount = countOccurrences(arr, leftResult.number, left, right);
        int rightCount = countOccurrences(arr, rightResult.number, left, right);

        if (leftCount > rightCount) {
            return new Result(leftResult.number, leftCount);
        } else {
            return new Result(rightResult.number, rightCount);
        }

    }

    private static int countOccurrences(int[] arr, int target, int left, int right) {
        int count = 0;
        for (int i = left; i <= right; i++) {
            if (arr[i] == target) {
                count++;
            }
        }
        return count;
    }
}